{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Items by Groups Respecting Dependencies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortItems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #项目管理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个项目，每个项目或者不属于任何小组，或者属于 <code>m</code> 个小组之一。<code>group[i]</code> 表示第 <code>i</code> 个项目所属的小组，如果第 <code>i</code> 个项目不属于任何小组，则 <code>group[i]</code> 等于 <code>-1</code>。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。</p>\n",
    "\n",
    "<p>请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>同一小组的项目，排序后在列表中彼此相邻。</li>\n",
    "\t<li>项目之间存在一定的依赖关系，我们用一个列表 <code>beforeItems</code> 来表示，其中 <code>beforeItems[i]</code> 表示在进行第 <code>i</code> 个项目前（位于第 <code>i</code> 个项目左侧）应该完成的所有项目。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 <strong>空列表 </strong>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/09/22/1359_ex1.png\" style=\"height: 181px; width: 191px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]\n",
    "<strong>输出：</strong>[6,3,4,1,5,2,0,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= m <= n <= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>group.length == beforeItems.length == n</code></li>\n",
    "\t<li><code>-1 <= group[i] <= m - 1</code></li>\n",
    "\t<li><code>0 <= beforeItems[i].length <= n - 1</code></li>\n",
    "\t<li><code>0 <= beforeItems[i][j] <= n - 1</code></li>\n",
    "\t<li><code>i != beforeItems[i][j]</code></li>\n",
    "\t<li><code>beforeItems[i]</code> 不含重复元素</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-items-by-groups-respecting-dependencies](https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-items-by-groups-respecting-dependencies](https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['8\\n2\\n[-1,-1,1,0,0,1,0,-1]\\n[[],[6],[5],[6],[3,6],[],[],[]]', '8\\n2\\n[-1,-1,1,0,0,1,0,-1]\\n[[],[6],[5],[6],[3],[],[4],[]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(m)]\n",
    "        indeque = [0] * n\n",
    "        q = []\n",
    "        for i, items in enumerate(beforeItems):\n",
    "            for item in items:\n",
    "                indeque[item] += 1\n",
    "        for i in range(n):\n",
    "            if indeque[i] == 0:\n",
    "                q.append(i)\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            u = q.pop()\n",
    "            cnt += 1\n",
    "            if group[u] == -1:\n",
    "                g.append([u])\n",
    "                group[u] = m\n",
    "                m += 1\n",
    "            else:\n",
    "                g[group[u]].append(u)\n",
    "            for v in beforeItems[u]:\n",
    "                indeque[v] -= 1\n",
    "                if indeque[v] == 0:\n",
    "                    q.append(v)\n",
    "        if cnt != n:\n",
    "            return []\n",
    "        # 组外排序\n",
    "        adj = [[] for _ in range(m)]\n",
    "        indeque = [0] * m\n",
    "        for i, items in enumerate(g):\n",
    "            st = set(items)\n",
    "            for item in items:\n",
    "                for x in beforeItems[item]:\n",
    "                    if x not in st:\n",
    "                        adj[i].append(group[x])\n",
    "                        indeque[group[x]] += 1\n",
    "        q = []\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if indeque[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            u = q.pop()\n",
    "            cnt += 1\n",
    "            ans += g[u]\n",
    "\n",
    "            for v in adj[u]:\n",
    "                indeque[v] -= 1\n",
    "                if indeque[v] == 0:\n",
    "                    q.append(v)\n",
    "        if cnt != m:\n",
    "            return []\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        itemind = [0] * n\n",
    "        groupind = [0] * m\n",
    "        groupitem = [[] for _ in range(m)]\n",
    "        nogroup = []\n",
    "        freeitem=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            cgroup = group[i]\n",
    "            if cgroup != -1:\n",
    "                groupitem[cgroup].append(i)\n",
    "            else:\n",
    "                nogroup.append(i)\n",
    "            itemind[i]=len(beforeItems[i])\n",
    "            for j in beforeItems[i]:\n",
    "                freeitem[j].append(i)\n",
    "                jgroup = group[j]\n",
    "                if jgroup != -1 and cgroup != -1 and jgroup!=cgroup:\n",
    "                    groupind[cgroup] += 1\n",
    "        ans = []\n",
    "        ndfs = []\n",
    "        for i in nogroup:\n",
    "            if itemind[i] == 0:\n",
    "                ndfs.append(i)\n",
    "\n",
    "        while ndfs:\n",
    "            c = ndfs.pop()\n",
    "            ans.append(c)\n",
    "            for d in freeitem[c]:\n",
    "                itemind[d] -= 1\n",
    "                gd = group[d]\n",
    "                if gd == -1:\n",
    "                    if itemind[d] == 0:\n",
    "                        ndfs.append(d)\n",
    "        gdfs = []\n",
    "        for i in range(m):\n",
    "            if groupind[i] == 0 and len(groupitem[i]) > 0:\n",
    "                gdfs.append(i)\n",
    "\n",
    "        while gdfs:\n",
    "            g = gdfs.pop()\n",
    "            dfs = []\n",
    "            for i in groupitem[g]:\n",
    "                if itemind[i] == 0:\n",
    "                    dfs.append(i)\n",
    "            while dfs:\n",
    "                c = dfs.pop()\n",
    "                ans.append(c)\n",
    "\n",
    "                for d in freeitem[c]:\n",
    "                    itemind[d] -= 1\n",
    "                    if group[d] == -1 or group[d] == g:                       \n",
    "                        if itemind[d] == 0:\n",
    "                            dfs.append(d)\n",
    "                    if group[d]!=-1 and group[d]!=g:\n",
    "                        groupind[group[d]] -= 1\n",
    "                        if groupind[group[d]] == 0:\n",
    "                            gdfs.append(group[d])\n",
    "        # print(ans)\n",
    "        if len(ans) == n:\n",
    "            return ans\n",
    "        else:\n",
    "            return []\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        #before means precondition\n",
    "        itemind = [len(x) for x in beforeItems] \n",
    "        groupind = [0] * m\n",
    "        groupitem = [[] for _ in range(m)]\n",
    "        nogroup = []\n",
    "        freeitem=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            cgroup = group[i]\n",
    "            if cgroup != -1:\n",
    "                groupitem[cgroup].append(i)\n",
    "            else:\n",
    "                nogroup.append(i)\n",
    "            for j in beforeItems[i]:\n",
    "                freeitem[j].append(i)\n",
    "                jgroup = group[j]\n",
    "                if jgroup != -1 and cgroup != -1 and jgroup!=cgroup:\n",
    "                    groupind[cgroup] += 1\n",
    "        ans = []\n",
    "        ndfs = []\n",
    "        for i in nogroup:\n",
    "            if itemind[i] == 0:\n",
    "                ndfs.append(i)\n",
    "\n",
    "        while ndfs:\n",
    "            c = ndfs.pop()\n",
    "            ans.append(c)\n",
    "            for d in freeitem[c]:\n",
    "                itemind[d] -= 1\n",
    "                gd = group[d]\n",
    "                if gd == -1:\n",
    "                    if itemind[d] == 0:\n",
    "                        ndfs.append(d)\n",
    "        gdfs = []\n",
    "        for i in range(m):\n",
    "            if groupind[i] == 0 and len(groupitem[i]) > 0:\n",
    "                gdfs.append(i)\n",
    "\n",
    "        while gdfs:\n",
    "            g = gdfs.pop()\n",
    "            dfs = []\n",
    "            for i in groupitem[g]:\n",
    "                if itemind[i] == 0:\n",
    "                    dfs.append(i)\n",
    "            while dfs:\n",
    "                c = dfs.pop()\n",
    "                ans.append(c)\n",
    "\n",
    "                for d in freeitem[c]:\n",
    "                    itemind[d] -= 1\n",
    "                    if group[d] == -1 or group[d] == g:                       \n",
    "                        if itemind[d] == 0:\n",
    "                            dfs.append(d)\n",
    "                    if group[d]!=-1 and group[d]!=g:\n",
    "                        groupind[group[d]] -= 1\n",
    "                        if groupind[group[d]] == 0:\n",
    "                            gdfs.append(group[d])\n",
    "\n",
    "        if len(ans) == n:\n",
    "            return ans\n",
    "        else:\n",
    "            return []\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "\n",
    "        maxg = max(group)\n",
    "        for i, g in enumerate(group):\n",
    "            if g == -1:\n",
    "                group[i] = maxg+1\n",
    "                maxg += 1\n",
    "        print (group)\n",
    "        # 预处理一下。\n",
    "        graph_g = [[] for i in range(maxg+1)]\n",
    "        for cur, p in enumerate(beforeItems):\n",
    "            for f in p:\n",
    "                g1, g2 = group[cur], group[f]\n",
    "                if g1 != g2 and g2 not in graph_g[g1]:\n",
    "                    graph_g[g1].append(g2)\n",
    "\n",
    "        print (graph_g)\n",
    "        # group 拓扑。\n",
    "        in_degree = [0] * (maxg + 1)\n",
    "        for i, t in enumerate(graph_g):\n",
    "            for j in t:\n",
    "                in_degree[j] += 1\n",
    "\n",
    "        q = deque()\n",
    "        for i, t in enumerate(in_degree):\n",
    "            if t == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        ans = []\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "            for j in graph_g[cur]:\n",
    "                in_degree[j] -= 1\n",
    "                if in_degree[j] == 0:\n",
    "                    q.append(j)\n",
    "\n",
    "        if sum(in_degree) != 0: return []\n",
    "\n",
    "        print (ans)\n",
    "\n",
    "        # item 拓扑。\n",
    "        item_in_degree = [0]*n\n",
    "        for i, t in enumerate(beforeItems):\n",
    "            for j in t:\n",
    "                item_in_degree[j] += 1\n",
    "\n",
    "        group_items = defaultdict(list)\n",
    "        for i, g in enumerate(group):\n",
    "            group_items[g].append(i)\n",
    "\n",
    "        new_ans = []\n",
    "        for g in ans:\n",
    "            q = deque()\n",
    "            for t in group_items[g]:\n",
    "                if item_in_degree[t] == 0:\n",
    "                    q.append(t)\n",
    "            cur = []\n",
    "            while q:\n",
    "                t = q.popleft()\n",
    "                cur.append(t)\n",
    "                for nxt in beforeItems[t]:\n",
    "                    item_in_degree[nxt] -= 1\n",
    "                    if item_in_degree[nxt] == 0 and nxt in group_items[g]:\n",
    "                        q.append(nxt)\n",
    "            if len(cur) != len(group_items[g]):\n",
    "                return []\n",
    "            new_ans += cur\n",
    "        new_ans.reverse()\n",
    "        return new_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m \n",
    "                m+=1\n",
    "        g1 =defaultdict(list)\n",
    "        g2 =defaultdict(list) \n",
    "        indegree1 = [0] * n \n",
    "        indegree2 = [0] * (2 * n ) \n",
    "        for i, vec in enumerate(beforeItems):\n",
    "            for u in vec:\n",
    "                g1[u].append(i)\n",
    "                indegree1[i] += 1\n",
    "                if group[u] != group[i]:\n",
    "                    indegree2[group[i]] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            g2[group[i]].append(i)\n",
    "            \n",
    "        Q = []\n",
    "        for i in range(n):\n",
    "            if indegree1[i] == 0 and indegree2[group[i]] == 0:\n",
    "                Q.append(i)\n",
    "        Q.sort(key=lambda x : group[x])\n",
    "        Q = deque(Q) \n",
    "        ans = []\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            ans.append(u) \n",
    "            for v in g1[u]:\n",
    "                indegree1[v] -= 1 \n",
    "                if group[u] != group[v]:\n",
    "                    indegree2[group[v]] -= 1 \n",
    "                if indegree2[group[v]] == 0:\n",
    "                    if group[v] == group[u]:\n",
    "                        if indegree1[v] == 0:\n",
    "                            Q.appendleft(v)\n",
    "                    else:\n",
    "                        for x in g2[group[v]]:\n",
    "                            if indegree1[x] == 0:\n",
    "                                Q.append(x)\n",
    "            \n",
    "        if len(ans) < n:\n",
    "            return []\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m \n",
    "                m+=1\n",
    "        g1 =defaultdict(list)\n",
    "        g2 =defaultdict(list) \n",
    "        indegree1 = [0] * n \n",
    "        indegree2 = [0] * (2 * n ) \n",
    "        for i, vec in enumerate(beforeItems):\n",
    "            for u in vec:\n",
    "                g1[u].append(i)\n",
    "                indegree1[i] += 1\n",
    "                if group[u] != group[i]:\n",
    "                    indegree2[group[i]] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            g2[group[i]].append(i)\n",
    "            \n",
    "        Q = []\n",
    "        vis = [0] * n \n",
    "        for i in range(n):\n",
    "            if indegree1[i] == 0 and indegree2[group[i]] == 0:\n",
    "                Q.append(i)\n",
    "                vis[i] = 1 \n",
    "        Q.sort(key=lambda x : group[x])\n",
    "        Q = deque(Q) \n",
    "        ans = []\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            ans.append(u) \n",
    "            for v in g1[u]:\n",
    "                indegree1[v] -= 1 \n",
    "                if group[u] != group[v]:\n",
    "                    indegree2[group[v]] -= 1 \n",
    "                if indegree2[group[v]] == 0:\n",
    "                    if group[v] == group[u]:\n",
    "                        if indegree1[v] == 0:\n",
    "                            Q.appendleft(v)\n",
    "                    else:\n",
    "                        for x in g2[group[v]]:\n",
    "                            if indegree1[x] == 0:\n",
    "                                Q.append(x)\n",
    "\n",
    "            \n",
    "        if len(ans) < n:\n",
    "            return []\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m \n",
    "                m+=1\n",
    "        g1 =defaultdict(list)\n",
    "        g2 =defaultdict(list) \n",
    "        indegree1 = [0] * n \n",
    "        indegree2 = [0] * (2 * n ) \n",
    "        for i, vec in enumerate(beforeItems):\n",
    "            for u in vec:\n",
    "                g1[u].append(i)\n",
    "                indegree1[i] += 1\n",
    "                if group[u] != group[i]:\n",
    "                    indegree2[group[i]] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            g2[group[i]].append(i)\n",
    "            \n",
    "        Q = []\n",
    "        for i in range(n):\n",
    "            if indegree1[i] == 0 and indegree2[group[i]] == 0:\n",
    "                Q.append(i)\n",
    "                \n",
    "        Q.sort(key=lambda x : group[x])\n",
    "        Q = deque(Q) \n",
    "        ans = []\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            ans.append(u) \n",
    "            for v in g1[u]:\n",
    "                indegree1[v] -= 1 \n",
    "                if group[u] != group[v]:\n",
    "                    indegree2[group[v]] -= 1 \n",
    "                if indegree2[group[v]] == 0:\n",
    "                    if group[v] == group[u]:\n",
    "                        if indegree1[v] == 0:\n",
    "                            Q.appendleft(v)\n",
    "                    else:\n",
    "                        for x in g2[group[v]]:\n",
    "                            if indegree1[x] == 0:\n",
    "                                Q.append(x)\n",
    "\n",
    "            \n",
    "        if len(ans) < n:\n",
    "            return []\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topological_sort(self,items,indegree,neighbors):\n",
    "        # 建立队列和访问顺序\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        \n",
    "        # 初始化队列\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                queue.append(item)\n",
    "                \n",
    "        if not queue: return []\n",
    "        \n",
    "        # BFS\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            res.append(cur)\n",
    "            \n",
    "            # 遍历邻居节点\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    queue.append(neighbor)\n",
    "                    \n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for task in range(n):\n",
    "            if group[task] == -1:\n",
    "                group[task] = max_group_id\n",
    "                max_group_id += 1\n",
    "                \n",
    "        task_indegree = [0] * n    \n",
    "        group_indegree = [0] * max_group_id\n",
    "        task_neighbors = [[] for _ in range(n)]\n",
    "        group_neighbors = [[] for _ in range(max_group_id)]\n",
    "        group_to_tasks = [[] for _ in range(max_group_id)]\n",
    "        \n",
    "        for task in range(n):\n",
    "            group_to_tasks[group[task]].append(task)\n",
    "            \n",
    "            for prerequisite in beforeItems[task]:\n",
    "                \n",
    "                # 判断相关联的两个项目是否属于同一组\n",
    "                if group[prerequisite] != group[task]:\n",
    "                    \n",
    "                    # 不是同组，给小组建图\n",
    "                    group_indegree[group[task]] += 1\n",
    "                    group_neighbors[group[prerequisite]].append(group[task])\n",
    "                else:\n",
    "                    # 同组，给组内项目建图\n",
    "                    task_indegree[task] += 1\n",
    "                    task_neighbors[prerequisite].append(task)\n",
    "                    \n",
    "\n",
    "        res = []\n",
    "        \n",
    "        # 得到小组的访问顺序\n",
    "        group_queue = self.topological_sort([i for i in range(max_group_id)],group_indegree,group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id: return []\n",
    "        \n",
    "        for group_id in group_queue:\n",
    "            # 得到每组项目的访问顺序\n",
    "            task_queue = self.topological_sort(group_to_tasks[group_id],task_indegree,task_neighbors)\n",
    "\n",
    "            if len(task_queue) != len(group_to_tasks[group_id]):\n",
    "                return []\n",
    "            res += task_queue\n",
    "                    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        max_group_id = max(group) + 1\n",
    "        # 根据组id找到对应所有项目\n",
    "        group_dict = defaultdict(list)\n",
    "        for i in range(len(group)):\n",
    "            if group[i] == -1:\n",
    "                group[i] = max_group_id\n",
    "                max_group_id += 1\n",
    "            group_dict[group[i]].append(i)\n",
    "        \n",
    "        group_road = defaultdict(list)\n",
    "        \n",
    "        for x,arr in enumerate(beforeItems):\n",
    "            for y in arr:\n",
    "                if group[x] == group[y]:\n",
    "                    continue\n",
    "                else:\n",
    "                    group_road[group[x]].append(group[y])\n",
    "        \n",
    "                \n",
    "        \n",
    "        # group 拓扑排序\n",
    "        # 先进先出\n",
    "        group_status = {}\n",
    "        group_que = deque()\n",
    "        def dfs_group(node):\n",
    "            group_status[node] = 1\n",
    "            for next in group_road[node]:\n",
    "                if next not in group_status:\n",
    "                    if not dfs_group(next):\n",
    "                        return False\n",
    "                \n",
    "                # 有环\n",
    "                if group_status[next] == 1:\n",
    "                    return False\n",
    "                    \n",
    "            group_status[node] = 2\n",
    "            group_que.appendleft(node)\n",
    "            return True\n",
    "            \n",
    "        # 遍历每个组id，生成拓扑排序栈\n",
    "        for node in range(max_group_id):\n",
    "            if node not in group_status:\n",
    "                if not dfs_group(node):\n",
    "                    # 组间有环就代表没有合适方案\n",
    "                    return []\n",
    "        \n",
    "        #print(group_que)\n",
    "        # 项目 拓扑排序\n",
    "        # 直接得结果\n",
    "        status = {}\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            status[node] = 1\n",
    "            for next in beforeItems[node]:\n",
    "                if next not in status:\n",
    "                    if not dfs(next):\n",
    "                        return False\n",
    "                \n",
    "                # 有环\n",
    "                if status[next] == 1:\n",
    "                    return False\n",
    "            \n",
    "            status[node] = 2\n",
    "            res.append(node)\n",
    "            return True\n",
    "                 \n",
    "        while group_que:\n",
    "            group_node = group_que.pop()\n",
    "            for node in group_dict[group_node]:\n",
    "                if node not in status:\n",
    "                    if not dfs(node):\n",
    "                        # 项目有环就代表没有合适方案\n",
    "                        return []\n",
    "        \n",
    "        return res\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topological_sort(self,items,indegree,neighbors):\n",
    "        # 建立队列和访问顺序\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        \n",
    "        # 初始化队列\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                queue.append(item)\n",
    "                \n",
    "        if not queue: return []\n",
    "        \n",
    "        # BFS\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            res.append(cur)\n",
    "            \n",
    "            # 遍历邻居节点\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    queue.append(neighbor)\n",
    "                    \n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for task in range(n):\n",
    "            if group[task] == -1:\n",
    "                group[task] = max_group_id\n",
    "                max_group_id += 1\n",
    "                \n",
    "        task_indegree = [0] * n    \n",
    "        group_indegree = [0] * max_group_id\n",
    "        task_neighbors = [[] for _ in range(n)]\n",
    "        group_neighbors = [[] for _ in range(max_group_id)]\n",
    "        group_to_tasks = [[] for _ in range(max_group_id)]\n",
    "        \n",
    "        for task in range(n):\n",
    "            group_to_tasks[group[task]].append(task)\n",
    "            \n",
    "            for prerequisite in beforeItems[task]:\n",
    "                \n",
    "                # 判断相关联的两个项目是否属于同一组\n",
    "                if group[prerequisite] != group[task]:\n",
    "                    \n",
    "                    # 不是同组，给小组建图\n",
    "                    group_indegree[group[task]] += 1\n",
    "                    group_neighbors[group[prerequisite]].append(group[task])\n",
    "                else:\n",
    "                    # 同组，给组内项目建图\n",
    "                    task_indegree[task] += 1\n",
    "                    task_neighbors[prerequisite].append(task)\n",
    "                    \n",
    "\n",
    "        res = []\n",
    "        \n",
    "        # 得到小组的访问顺序\n",
    "        group_queue = self.topological_sort([i for i in range(max_group_id)],group_indegree,group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id: return []\n",
    "        \n",
    "        for group_id in group_queue:\n",
    "            # 得到每组项目的访问顺序\n",
    "            task_queue = self.topological_sort(group_to_tasks[group_id],task_indegree,task_neighbors)\n",
    "\n",
    "            if len(task_queue) != len(group_to_tasks[group_id]):\n",
    "                return []\n",
    "            res += task_queue\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        groupedge=collections.defaultdict(list)\n",
    "        groupdegree=collections.Counter()\n",
    "        groupnumber=collections.defaultdict(set)\n",
    "        indeg=[0]*n\n",
    "        edge=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:\n",
    "                group[i]=n+i\n",
    "                groupnumber[i+n].add(i)\n",
    "            else:\n",
    "                groupnumber[group[i]].add(i)\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                if group[i]==group[j]:\n",
    "                    indeg[i]+=1\n",
    "                    edge[j].append(i)\n",
    "                    continue\n",
    "                groupdegree[group[i]]+=1\n",
    "                groupedge[group[j]].append(group[i])\n",
    "        print(groupnumber,groupdegree,groupedge)\n",
    "        q=[] \n",
    "        for key in groupnumber:\n",
    "            if groupdegree[key]==0:\n",
    "                q.append(key)\n",
    "        \n",
    "        def findorder(g):\n",
    "            ls=list(groupnumber[g])\n",
    "            if len(ls)==1:\n",
    "                return ls\n",
    "            q=[]\n",
    "            ret=[]\n",
    "            for i in ls:\n",
    "                if indeg[i]==0:\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                tp=q.pop()\n",
    "                ret.append(tp)\n",
    "                for j in edge[tp]:\n",
    "                    indeg[j]-=1\n",
    "                    if indeg[j]==0:\n",
    "                        q.append(j)\n",
    "            if len(ret)!=len(ls):\n",
    "                return []\n",
    "            return ret\n",
    "        ret=[]\n",
    "        while q:\n",
    "            tp=q.pop()\n",
    "            tpl=findorder(tp)\n",
    "            if not tpl:\n",
    "                return []\n",
    "            for i in groupedge[tp]:\n",
    "                groupdegree[i]-=1\n",
    "                if groupdegree[i]==0:\n",
    "                    q.append(i)\n",
    "            ret+=tpl \n",
    "        for key in groupdegree:\n",
    "            if groupdegree[key]!=0:\n",
    "                return []\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n, m, group, beforeItems):\n",
    "        # Step 1: Data preprocessing - Assign group numbers to items without a group\n",
    "        for i in range(len(group)):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "\n",
    "        # Step 2: Instantiate adjacency lists for groups and items\n",
    "        groupAdj = [[] for _ in range(m)]\n",
    "        itemAdj = [[] for _ in range(n)]\n",
    "\n",
    "        # Step 3: Build graphs and calculate in-degrees\n",
    "        groupsIndegree = [0] * m\n",
    "        itemsIndegree = [0] * n\n",
    "\n",
    "        for i in range(len(group)):\n",
    "            currentGroup = group[i]\n",
    "            for beforeItem in beforeItems[i]:\n",
    "                beforeGroup = group[beforeItem]\n",
    "                if beforeGroup != currentGroup:\n",
    "                    groupAdj[beforeGroup].append(currentGroup)\n",
    "                    groupsIndegree[currentGroup] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for beforeItem in beforeItems[i]:\n",
    "                itemAdj[beforeItem].append(i)\n",
    "                itemsIndegree[i] += 1\n",
    "\n",
    "        # Step 4: Get topological sorting results for groups and items\n",
    "        groupsList = self.topologicalSort(groupAdj, groupsIndegree, m)\n",
    "        if not groupsList:\n",
    "            return []\n",
    "\n",
    "        itemsList = self.topologicalSort(itemAdj, itemsIndegree, n)\n",
    "        if not itemsList:\n",
    "            return []\n",
    "\n",
    "        # Step 5: Create a mapping of groups to items and replace group sorting with item sorting\n",
    "        groups2Items = defaultdict(list)\n",
    "        for item in itemsList:\n",
    "            groups2Items[group[item]].append(item)\n",
    "\n",
    "        # Step 6: Replace group sorting with item sorting\n",
    "        res = []\n",
    "        for groupId in groupsList:\n",
    "            items = groups2Items[groupId]\n",
    "            res.extend(items)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def topologicalSort(self, adj, inDegree, n):\n",
    "        res = []\n",
    "        queue = deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if inDegree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            front = queue.popleft()\n",
    "            res.append(front)\n",
    "            for successor in adj[front]:\n",
    "                inDegree[successor] -= 1\n",
    "                if inDegree[successor] == 0:\n",
    "                    queue.append(successor)\n",
    "\n",
    "        if len(res) == n:\n",
    "            return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # 给每个未分组的项目分组\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "        # graph和indegree存储整个项目的图，其中graph存储有向边，indegree存储每个项目的入度\n",
    "        graph = [[] for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        # groupid存储所有的小组以及每个小组所属的项目，用字典key表示项目，values表示属于该小组的项目\n",
    "        groupid = collections.defaultdict(list)\n",
    "        # graph1和indgreetemp存储小组的图以及每个小组的入度，由于下面的统计方法肯定会有重复边出现，所以后面会去重\n",
    "        graph1 =collections.defaultdict(list)\n",
    "        indegreetemp = collections.defaultdict(list)\n",
    "        # 遍历每个项目，以及该项目的前置项目，构建小组图和整个项目图\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                graph[j].append(i)\n",
    "                graph1[group[j]].append(group[i])\n",
    "            indegree[i] = len(beforeItems[i])\n",
    "            indegreetemp[group[i]].extend([group[w] for w in beforeItems[i]])\n",
    "            groupid[group[i]].append(i)\n",
    "        # 对小组图存储有向边的graph1进行去重，统计每个小组的入度存储到indegree1\n",
    "        graph1 = {i: list(set(graph1[i])) for i in groupid.keys()}\n",
    "        indegree1 = {i: len(set(indegreetemp[i])-set([i])) for i in groupid.keys()}\n",
    "        # 拓扑排序函数，给一个有向图，返回其拓扑排序，如果存在环，即不能拓扑排序，返回空列表\n",
    "        # 其中indegree代表入度，graph代表有向边，items代表该图的每一个顶点\n",
    "        def topolopy(indegree, graph, items):\n",
    "            q = []\n",
    "            res = []\n",
    "            for i in items:\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                node = q.pop(0)\n",
    "                res.append(node)\n",
    "                for i in graph[node]:\n",
    "                    indegree[i] -= 1\n",
    "                    if i in items and indegree[i] == 0:\n",
    "                        q.append(i)\n",
    "            return [] if len(res) != len(items) else res\n",
    "            \n",
    "\n",
    "        sol = []\n",
    "        # 对小组组成图进行拓扑排序，返回小组的排序数组，存到order\n",
    "        order = topolopy(indegree1, graph1, list(groupid.keys()))\n",
    "        if len(order) == 0:\n",
    "            return []\n",
    "        # 对order中的每个小组所属项目构成的图进行拓扑排序，得到的结果存储到最后的答案sol中\n",
    "        for i in order:\n",
    "            temp = topolopy(indegree, graph, groupid[i])\n",
    "            if len(temp) > 0:\n",
    "                sol.extend(temp)\n",
    "            else:\n",
    "                return []\n",
    "        return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # 将不属于任何组的单独成组赋予组编号并记录每个组的成员\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "            dct[group[i]].append(i)\n",
    "        # 记录组间的拓扑关系与组内的拓扑关系\n",
    "        inter_edge = defaultdict(list)\n",
    "        inner_edge = defaultdict(lambda: defaultdict(list))\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                if group[i] == group[j]:\n",
    "                    inner_edge[group[i]][j].append(i)\n",
    "                else:\n",
    "                    inter_edge[group[j]].append(group[i])\n",
    "\n",
    "        # 检查网络拓扑是否可行\n",
    "        def check(edge, nodes):\n",
    "            degree = defaultdict(int)\n",
    "            for j in edge:\n",
    "                for i in edge[j]:\n",
    "                    degree[i] += 1\n",
    "            ans = []\n",
    "            stack = [i for i in nodes if not degree[i]]\n",
    "            while stack:\n",
    "                ans.extend(stack)\n",
    "                nex = []\n",
    "                for j in stack:\n",
    "                    for i in edge[j]:\n",
    "                        degree[i] -= 1\n",
    "                        if not degree[i]:\n",
    "                            nex.append(i)\n",
    "                stack = nex[:]\n",
    "            return ans if len(ans) == len(nodes) else []\n",
    "        \n",
    "        # 确定组间的可行顺序\n",
    "        inter_order = check(inter_edge, list(set(group)))\n",
    "        if not inter_order:\n",
    "            return inter_order\n",
    "        # 确定组内的可行的顺序        \n",
    "        res = []\n",
    "        for g in inter_order:\n",
    "            inner_order = check(inner_edge[g], dct[g])\n",
    "            if not inner_order:\n",
    "                return inner_order\n",
    "            res.extend(inner_order)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # 将不属于任何组的单独成组赋予组编号并记录每个组的成员\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "            dct[group[i]].append(i)\n",
    "        # 记录组间的拓扑关系与组内的拓扑关系\n",
    "        inter_edge = defaultdict(list)\n",
    "        inner_edge = defaultdict(lambda: defaultdict(list))\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                if group[i] == group[j]:\n",
    "                    inner_edge[group[i]][j].append(i)\n",
    "                else:\n",
    "                    inter_edge[group[j]].append(group[i])\n",
    "\n",
    "        # 检查网络拓扑是否可行\n",
    "        def check(edge, nodes):\n",
    "            degree = defaultdict(int)\n",
    "            for j in edge:\n",
    "                for i in edge[j]:\n",
    "                    degree[i] += 1\n",
    "            ans = []\n",
    "            stack = [i for i in nodes if not degree[i]]\n",
    "            while stack:\n",
    "                ans.extend(stack)\n",
    "                nex = []\n",
    "                for j in stack:\n",
    "                    for i in edge[j]:\n",
    "                        degree[i] -= 1\n",
    "                        if not degree[i]:\n",
    "                            nex.append(i)\n",
    "                stack = nex[:]\n",
    "            return ans if len(ans) == len(nodes) else []\n",
    "        \n",
    "        # 确定组间的可行顺序\n",
    "        inter_order = check(inter_edge, list(set(group)))\n",
    "        if not inter_order:\n",
    "            return inter_order\n",
    "        # 确定组内的可行的顺序        \n",
    "        res = []\n",
    "        for g in inter_order:\n",
    "            inner_order = check(inner_edge[g], dct[g])\n",
    "            if not inner_order:\n",
    "                return inner_order\n",
    "            res.extend(inner_order)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: list[int], beforeItems: list[list[int]]) -> list[int]:\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "        # graph和indegree存储整个项目的图，其中graph存储有向边，indegree存储每个项目的入度\n",
    "        graph = [[] for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        # groupid存储所有的小组以及每个小组所属的项目，用字典key表示项目，values表示属于该小组的项目\n",
    "        groupid = collections.defaultdict(list)\n",
    "        # graph1和indgreetemp存储小组的图以及每个小组的入度，由于下面的统计方法肯定会有重复边出现，所以后面会去重\n",
    "        graph1 = collections.defaultdict(list)\n",
    "        indegreetemp = collections.defaultdict(list)\n",
    "        # 遍历每个项目，以及该项目的前置项目，构建小组图和整个项目图\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                graph[j].append(i)\n",
    "                graph1[group[j]].append(group[i])\n",
    "            indegree[i] = len(beforeItems[i])\n",
    "            indegreetemp[group[i]].extend([group[w] for w in beforeItems[i]])\n",
    "            groupid[group[i]].append(i)\n",
    "        # 对小组图存储有向边的graph1进行去重，统计每个小组的入度存储到indegree1\n",
    "        graph1 = {i: list(set(graph1[i])) for i in groupid.keys()}\n",
    "        indegree1 = {i: len(set(indegreetemp[i]) - set([i])) for i in groupid.keys()}\n",
    "\n",
    "        # 拓扑排序函数，给一个有向图，返回其拓扑排序，如果存在环，即不能拓扑排序，返回空列表\n",
    "        # 其中indegree代表入度，graph代表有向边，items代表该图的每一个顶点\n",
    "        def topolopy(indegree, graph, items):\n",
    "            q = []\n",
    "            res = []\n",
    "            for i in items:\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                node = q.pop(0)\n",
    "                res.append(node)\n",
    "                for i in graph[node]:\n",
    "                    indegree[i] -= 1\n",
    "                    if i in items and indegree[i] == 0:\n",
    "                        q.append(i)\n",
    "            return [] if len(res) != len(items) else res\n",
    "\n",
    "        sol = []\n",
    "        # 对小组组成图进行拓扑排序，返回小组的排序数组，存到order\n",
    "        order = topolopy(indegree1, graph1, list(groupid.keys()))\n",
    "        if len(order) == 0:\n",
    "            return []\n",
    "        # 对order中的每个小组所属项目构成的图进行拓扑排序，得到的结果存储到最后的答案sol中\n",
    "        for i in order:\n",
    "            temp = topolopy(indegree, graph, groupid[i])\n",
    "            if len(temp) > 0:\n",
    "                sol.extend(temp)\n",
    "            else:\n",
    "                return []\n",
    "        return sol\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # group中所含有的项目\n",
    "        dct = defaultdict(list) \n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "            dct[group[i]].append(i)\n",
    "\n",
    "        inter_edge = defaultdict(list)\n",
    "        inner_edge = defaultdict(lambda :defaultdict(list))\n",
    "\n",
    "        for i in range(n):\n",
    "            befor = beforeItems[i]\n",
    "            for j in befor:\n",
    "                if group[i] != group[j]:\n",
    "                    inter_edge[group[j]].append(group[i])\n",
    "                else:\n",
    "                    inner_edge[group[i]][j].append(i)\n",
    "        \n",
    "        def top_sort(edge, nodes):\n",
    "            res = []\n",
    "            q = deque()\n",
    "            deg = defaultdict(int)\n",
    "\n",
    "            for i in edge:\n",
    "                for nxt in edge[i]:\n",
    "                    deg[nxt] += 1\n",
    "            \n",
    "            for node in nodes:\n",
    "                if not deg[node]:\n",
    "                    q.append(node)\n",
    "            \n",
    "            while q:\n",
    "                res.append(q.popleft())\n",
    "                for nxt in edge[res[-1]]:\n",
    "                    deg[nxt] -= 1\n",
    "                    if not deg[nxt]: q.append(nxt)\n",
    "            return res if len(res) == len(nodes) else []\n",
    "\n",
    "        group_order = top_sort(inter_edge, list(set(group)))\n",
    "        if not group_order: return group_order\n",
    "\n",
    "        ans = []\n",
    "        for i in group_order:\n",
    "            res = top_sort(inner_edge[i], dct[i])\n",
    "            if not res: return res\n",
    "            ans.extend(res)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "\n",
    "        dic = defaultdict(list)\n",
    "        cur = max(group) + 1\n",
    "        for i, g in enumerate(group):\n",
    "            if g == -1:\n",
    "                group[i] = cur\n",
    "                cur += 1\n",
    "            dic[group[i]].append(i)\n",
    "\n",
    "        outer = defaultdict(list)\n",
    "        inner = defaultdict(lambda: defaultdict(list))\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                if group[i] == group[j]:\n",
    "                    inner[group[i]][j].append(i)\n",
    "                else:\n",
    "                    outer[group[j]].append(group[i])\n",
    "        \n",
    "\n",
    "        def bfs(edges, nodes):\n",
    "            degree = defaultdict(int)\n",
    "            for x in edges:\n",
    "                for y in edges[x]:\n",
    "                    degree[y] += 1\n",
    "            q = [i for i in nodes if degree[i] == 0]\n",
    "            arr = []\n",
    "            while q:\n",
    "                arr.extend(q)\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for node in tmp:\n",
    "                    for v in edges[node]:\n",
    "                        degree[v] -= 1\n",
    "                        if degree[v] == 0:\n",
    "                            q.append(v) \n",
    "            return arr if len(arr) == len(nodes) else []\n",
    "\n",
    "        res = []\n",
    "        \n",
    "        arr = bfs(outer, list(set(group)))\n",
    "        if not arr:\n",
    "            # print(1)\n",
    "            return []\n",
    "        \n",
    "        for g in arr:\n",
    "            cur = bfs(inner[g], dic[g])\n",
    "            if not cur:\n",
    "                return []\n",
    "            res.extend(cur)        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # 给每个未分组的项目分组\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "        # graph和indegree存储整个项目的图，其中graph存储有向边，indegree存储每个项目的入度\n",
    "        graph = [[] for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        # groupid存储所有的小组以及每个小组所属的项目，用字典key表示项目，values表示属于该小组的项目\n",
    "        groupid = collections.defaultdict(list)\n",
    "        # graph1和indgreetemp存储小组的图以及每个小组的入度，由于下面的统计方法肯定会有重复边出现，所以后面会去重\n",
    "        graph1 =collections.defaultdict(list)\n",
    "        indegreetemp = collections.defaultdict(list)\n",
    "        # 遍历每个项目，以及该项目的前置项目，构建小组图和整个项目图\n",
    "        for i in range(n):\n",
    "            for j in beforeItems[i]:\n",
    "                graph[j].append(i)\n",
    "                graph1[group[j]].append(group[i])\n",
    "            indegree[i] = len(beforeItems[i])\n",
    "            indegreetemp[group[i]].extend([group[w] for w in beforeItems[i]])\n",
    "            groupid[group[i]].append(i)\n",
    "        # 对小组图存储有向边的graph1进行去重，统计每个小组的入度存储到indegree1\n",
    "        graph1 = {i: list(set(graph1[i])) for i in groupid.keys()}\n",
    "        indegree1 = {i: len(set(indegreetemp[i])-set([i])) for i in groupid.keys()}\n",
    "        # 拓扑排序函数，给一个有向图，返回其拓扑排序，如果存在环，即不能拓扑排序，返回空列表\n",
    "        # 其中indegree代表入度，graph代表有向边，items代表该图的每一个顶点\n",
    "        def topolopy(indegree, graph, items):\n",
    "            q = []\n",
    "            res = []\n",
    "            for i in items:\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                node = q.pop(0)\n",
    "                res.append(node)\n",
    "                for i in graph[node]:\n",
    "                    indegree[i] -= 1\n",
    "                    if i in items and indegree[i] == 0:\n",
    "                        q.append(i)\n",
    "            return [] if len(res) != len(items) else res\n",
    "            \n",
    "\n",
    "        sol = []\n",
    "        # 对小组组成图进行拓扑排序，返回小组的排序数组，存到order\n",
    "        order = topolopy(indegree1, graph1, list(groupid.keys()))\n",
    "        if len(order) == 0:\n",
    "            return []\n",
    "        # 对order中的每个小组所属项目构成的图进行拓扑排序，得到的结果存储到最后的答案sol中\n",
    "        for i in order:\n",
    "            temp = topolopy(indegree, graph, groupid[i])\n",
    "            if len(temp) > 0:\n",
    "                sol.extend(temp)\n",
    "            else:\n",
    "                return []\n",
    "        return sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        item_ind = collections.defaultdict(int)\n",
    "        group_ind = collections.defaultdict(int)\n",
    "        group_to_item = collections.defaultdict(list)\n",
    "        item_to_group = collections.defaultdict(int)\n",
    "        group_g = collections.defaultdict(list)\n",
    "        item_g = collections.defaultdict(list)\n",
    "        for i, gr in enumerate(group):\n",
    "            if gr != -1:\n",
    "                item_to_group[i] = gr\n",
    "                group_to_item[gr].append(i)\n",
    "        for i, gr in enumerate(group):\n",
    "            if gr == -1:\n",
    "                tmp = len(group_to_item)\n",
    "                item_to_group[i] = tmp\n",
    "                group_to_item[tmp].append(i)\n",
    "        for i, bs in enumerate(beforeItems):\n",
    "            for b in bs:\n",
    "                i_group = item_to_group[i]\n",
    "                b_group = item_to_group[b]\n",
    "                if i_group != b_group:\n",
    "                    group_ind[i_group] += 1\n",
    "                    group_g[b_group].append(i_group)\n",
    "                item_ind[i] += 1\n",
    "                item_g[b].append(i)\n",
    "        order = []\n",
    "        q = deque()\n",
    "        for k, v in group_to_item.items():\n",
    "            if not group_ind[k]:\n",
    "                q.append(k)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            order.append(x)\n",
    "            for y in group_g[x]:\n",
    "                group_ind[y] -= 1\n",
    "                if not group_ind[y]:\n",
    "                    q.append(y)\n",
    "        ans = []\n",
    "        for ls in order:\n",
    "            q = deque()\n",
    "            for x in group_to_item[ls]:\n",
    "                if not item_ind[x]:\n",
    "                    q.append(x)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                ans.append(x)\n",
    "                for y in item_g[x]:\n",
    "                    item_ind[y] -= 1\n",
    "                    if not item_ind[y] and item_to_group[y] == ls:\n",
    "                        q.append(y)\n",
    "        return ans if len(ans) == len(group) else []\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n+2*m)]\n",
    "        d = [0] * (n+2*m)\n",
    "        for x,l in enumerate(beforeItems):\n",
    "            for y in l:\n",
    "                if group[x] == group[y]:\n",
    "                    g[y].append(x)\n",
    "                    d[x] += 1\n",
    "                    continue\n",
    "                t = x\n",
    "                if group[t] != -1:\n",
    "                    g[n+group[t]].append(t)\n",
    "                    d[t] += 1\n",
    "                    t = n+group[t]\n",
    "                if group[y] != -1:\n",
    "                    g[y].append(n+m+group[y])\n",
    "                    d[n+m+group[y]] += 1\n",
    "                    y = n+m+group[y]\n",
    "                g[y].append(t)\n",
    "                d[t] += 1\n",
    "        q = list(filter(lambda i:d[i]==0,range(n)))\n",
    "        for x in q:\n",
    "            if group[x] != -1:\n",
    "                g[n+group[x]].append(x)\n",
    "                d[x] += 1\n",
    "        q = list(filter(lambda i:d[i]==0,range(n+m)))\n",
    "        ans = []\n",
    "        while q:\n",
    "            new_q = []\n",
    "            finish_group = []\n",
    "            for x in q:\n",
    "                if x >= n+m: continue\n",
    "                if x >= n: finish_group.append(x-n)\n",
    "                else:\n",
    "                    ans.append(x)\n",
    "                    for y in g[x]:\n",
    "                        d[y] -= 1\n",
    "                        if d[y] == 0:\n",
    "                            new_q.append(y)\n",
    "            for gi in finish_group:\n",
    "                group_q = [gi+n]\n",
    "                while group_q:\n",
    "                    x = group_q.pop()\n",
    "                    if x < n: ans.append(x)\n",
    "                    for y in g[x]:\n",
    "                        d[y] -= 1\n",
    "                        if d[y] == 0 and y<n:\n",
    "                            group_q.append(y)\n",
    "                if d[n+m+gi] != 0: return []\n",
    "                for y in g[n+m+gi]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 0: new_q.append(y)\n",
    "            q = new_q\n",
    "        return ans if len(ans) == n else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        item_ind = collections.defaultdict(int)\n",
    "        group_ind = collections.defaultdict(int)\n",
    "        group_to_item = collections.defaultdict(list)\n",
    "        item_to_group = collections.defaultdict(int)\n",
    "        group_g = collections.defaultdict(list)\n",
    "        item_g = collections.defaultdict(list)\n",
    "        for i, gr in enumerate(group):\n",
    "            if gr != -1:\n",
    "                item_to_group[i] = gr\n",
    "                group_to_item[gr].append(i)\n",
    "        for i, gr in enumerate(group):\n",
    "            if gr == -1:\n",
    "                tmp = len(group_to_item)\n",
    "                item_to_group[i] = tmp\n",
    "                group_to_item[tmp].append(i)\n",
    "        for i, bs in enumerate(beforeItems):\n",
    "            for b in bs:\n",
    "                i_group = item_to_group[i]\n",
    "                b_group = item_to_group[b]\n",
    "                if i_group != b_group:\n",
    "                    group_ind[i_group] += 1\n",
    "                    group_g[b_group].append(i_group)\n",
    "                item_ind[i] += 1\n",
    "                item_g[b].append(i)\n",
    "        order = []\n",
    "        q = deque()\n",
    "        for k, v in group_to_item.items():\n",
    "            if not group_ind[k]:\n",
    "                q.append(k)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            order.append(x)\n",
    "            for y in group_g[x]:\n",
    "                group_ind[y] -= 1\n",
    "                if not group_ind[y]:\n",
    "                    q.append(y)\n",
    "        ans = []\n",
    "        for ls in order:\n",
    "            q = deque()\n",
    "            for x in group_to_item[ls]:\n",
    "                if not item_ind[x]:\n",
    "                    q.append(x)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                ans.append(x)\n",
    "                for y in item_g[x]:\n",
    "                    item_ind[y] -= 1\n",
    "                    if not item_ind[y] and item_to_group[y] == ls:\n",
    "                        q.append(y)\n",
    "        return ans if len(ans) == len(group) else []\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        item_ind = collections.defaultdict(int)\n",
    "        group_ind = collections.defaultdict(int)\n",
    "        group_to_item = collections.defaultdict(list)\n",
    "        item_to_group = collections.defaultdict(int)\n",
    "        group_g = collections.defaultdict(list)\n",
    "        item_g = collections.defaultdict(list)\n",
    "        for i, gr in enumerate(group):\n",
    "            if gr != -1:\n",
    "                item_to_group[i] = gr\n",
    "                group_to_item[gr].append(i)\n",
    "        for i, gr in enumerate(group):\n",
    "            if gr == -1:\n",
    "                tmp = len(group_to_item)\n",
    "                item_to_group[i] = tmp\n",
    "                group_to_item[tmp].append(i)\n",
    "        for i, bs in enumerate(beforeItems):\n",
    "            for b in bs:\n",
    "                i_group = item_to_group[i]\n",
    "                b_group = item_to_group[b]\n",
    "                if i_group != b_group:\n",
    "                    group_ind[i_group] += 1\n",
    "                    group_g[b_group].append(i_group)\n",
    "                item_ind[i] += 1\n",
    "                item_g[b].append(i)\n",
    "        order = []\n",
    "        q = deque()\n",
    "        for k, v in group_to_item.items():\n",
    "            if not group_ind[k]:\n",
    "                q.append(k)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            order.append(x)\n",
    "            for y in group_g[x]:\n",
    "                group_ind[y] -= 1\n",
    "                if not group_ind[y]:\n",
    "                    q.append(y)\n",
    "        ans = []\n",
    "        for ls in order:\n",
    "            q = deque()\n",
    "            for x in group_to_item[ls]:\n",
    "                if not item_ind[x]:\n",
    "                    q.append(x)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                ans.append(x)\n",
    "                for y in item_g[x]:\n",
    "                    item_ind[y] -= 1\n",
    "                    if not item_ind[y] and item_to_group[y] == ls:\n",
    "                        q.append(y)\n",
    "        return ans if len(ans) == len(group) else []\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n+2*m)]\n",
    "        d = [0] * (n+2*m)\n",
    "        for x,l in enumerate(beforeItems):\n",
    "            print(x,group[x])\n",
    "            for y in l:\n",
    "                print('\\t',y,group[y])\n",
    "                if group[x] == group[y]:\n",
    "                    g[y].append(x)\n",
    "                    d[x] += 1\n",
    "                    continue\n",
    "                t = x\n",
    "                if group[t] != -1:\n",
    "                    g[n+group[t]].append(t)\n",
    "                    d[t] += 1\n",
    "                    t = n+group[t]\n",
    "                if group[y] != -1:\n",
    "                    g[y].append(n+m+group[y])\n",
    "                    d[n+m+group[y]] += 1\n",
    "                    y = n+m+group[y]\n",
    "                g[y].append(t)\n",
    "                d[t] += 1\n",
    "        q = list(filter(lambda i:d[i]==0,range(n)))\n",
    "        for x in q:\n",
    "            if group[x] != -1:\n",
    "                g[n+group[x]].append(x)\n",
    "                d[x] += 1\n",
    "        q = list(filter(lambda i:d[i]==0,range(n+m)))\n",
    "        ans = []\n",
    "        while q:\n",
    "            new_q = []\n",
    "            finish_group = []\n",
    "            for x in q:\n",
    "                if x >= n+m: continue\n",
    "                if x >= n: finish_group.append(x-n)\n",
    "                else:\n",
    "                    ans.append(x)\n",
    "                    for y in g[x]:\n",
    "                        d[y] -= 1\n",
    "                        if d[y] == 0:\n",
    "                            new_q.append(y)\n",
    "            for gi in finish_group:\n",
    "                group_q = [gi+n]\n",
    "                while group_q:\n",
    "                    x = group_q.pop()\n",
    "                    if x < n: ans.append(x)\n",
    "                    for y in g[x]:\n",
    "                        d[y] -= 1\n",
    "                        if d[y] == 0 and y<n:\n",
    "                            group_q.append(y)\n",
    "                if d[n+m+gi] != 0: return []\n",
    "                for y in g[n+m+gi]:\n",
    "                    d[y] -= 1\n",
    "                    if d[y] == 0: new_q.append(y)\n",
    "            q = new_q\n",
    "        return ans if len(ans) == n else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        record = collections.defaultdict(list)\n",
    "        \n",
    "        indegree = [0 for _ in range(n)]\n",
    "        edge = collections.defaultdict(list)\n",
    "\n",
    "        group_len = m\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = group_len\n",
    "                group_len += 1\n",
    "\n",
    "        for i, num in enumerate(group):\n",
    "            record[num].append(i)\n",
    "\n",
    "        group_indegree = [0 for _ in range(group_len)]\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "\n",
    "        for key, values in enumerate(beforeItems):\n",
    "            for value in values:\n",
    "                if group[key] != group[value]:\n",
    "                    group_indegree[group[key]] += 1\n",
    "                    group_neighbors[group[value]].append(group[key])\n",
    "                else:\n",
    "                    indegree[key] += 1\n",
    "                    edge[value].append(key)\n",
    "        print(group_neighbors, group_indegree)\n",
    "        group_order = []\n",
    "        queue = []\n",
    "        for i in range(group_len):\n",
    "            if group_indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            group_index = queue.pop(0)\n",
    "            group_order.append(group_index)\n",
    "            for nxt in group_neighbors[group_index]:\n",
    "                group_indegree[nxt] -= 1\n",
    "                if group_indegree[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "        \n",
    "        if len(group_order) != group_len:\n",
    "            return []\n",
    "        print(group_order)\n",
    "        res = []\n",
    "        for group_index in group_order:\n",
    "            temp = []\n",
    "            queue = []\n",
    "            for item in record[group_index]:\n",
    "                if indegree[item] == 0:\n",
    "                    queue.append(item)\n",
    "            while queue:\n",
    "                node = queue.pop(0)\n",
    "                temp.append(node)\n",
    "                for nxt in edge[node]:\n",
    "                    indegree[nxt] -= 1\n",
    "                    if indegree[nxt] == 0:\n",
    "                        queue.append(nxt)\n",
    "            if len(temp) != len(record[group_index]):\n",
    "                return []\n",
    "            res += temp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        #item拓扑排序\n",
    "        itemlist=collections.defaultdict(list)\n",
    "        itemcount=collections.Counter()\n",
    "        for i,x in enumerate(beforeItems):\n",
    "            for j in x:\n",
    "                itemlist[j].append(i)\n",
    "                itemcount[i]+=1\n",
    "        itemsort=[i for i in range(n) if itemcount[i]==0]\n",
    "        queue=deque(itemsort)\n",
    "        while queue:\n",
    "            x=queue.popleft()\n",
    "            for i in itemlist[x]:\n",
    "                itemcount[i]-=1\n",
    "                if itemcount[i]==0:\n",
    "                    queue.append(i)\n",
    "                    itemsort.append(i)\n",
    "        if len(itemsort)!=n:\n",
    "            return []\n",
    "        \n",
    "\n",
    "        #group拓扑排序\n",
    "        id=m-1\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:\n",
    "                id+=1\n",
    "                group[i]=id\n",
    "        grouplist=collections.defaultdict(list)\n",
    "        groupcount=collections.Counter()\n",
    "        for i,x in enumerate(beforeItems):\n",
    "            for j in x:\n",
    "                if group[j]==group[i]:\n",
    "                    continue\n",
    "                grouplist[group[j]].append(group[i])\n",
    "                groupcount[group[i]]+=1\n",
    "        groupsort=[i for i in range(id+1) if groupcount[i]==0]\n",
    "        queue=deque(groupsort)\n",
    "        while queue:\n",
    "            x=queue.popleft()\n",
    "            for i in grouplist[x]:\n",
    "                groupcount[i]-=1\n",
    "                if groupcount[i]==0:\n",
    "                    queue.append(i)\n",
    "                    groupsort.append(i)\n",
    "        if len(groupsort)!=id+1:\n",
    "            return []\n",
    "\n",
    "        #映射\n",
    "        fenqu=collections.defaultdict(list)\n",
    "        ans=[]\n",
    "        for i in itemsort:\n",
    "            fenqu[group[i]].append(i)\n",
    "        for i in groupsort:\n",
    "            ans.extend(fenqu[i])\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        #item拓扑排序\n",
    "        itemlist=collections.defaultdict(list)\n",
    "        itemcount=collections.Counter()\n",
    "        for i,x in enumerate(beforeItems):\n",
    "            for j in x:\n",
    "                itemlist[j].append(i)\n",
    "                itemcount[i]+=1\n",
    "        itemsort=[i for i in range(n) if itemcount[i]==0]\n",
    "        queue=deque(itemsort)\n",
    "        while queue:\n",
    "            x=queue.popleft()\n",
    "            for i in itemlist[x]:\n",
    "                itemcount[i]-=1\n",
    "                if itemcount[i]==0:\n",
    "                    queue.append(i)\n",
    "                    itemsort.append(i)\n",
    "        if len(itemsort)!=n:\n",
    "            return []\n",
    "        \n",
    "\n",
    "        #group拓扑排序\n",
    "        id=m-1\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:\n",
    "                id+=1\n",
    "                group[i]=id\n",
    "        grouplist=collections.defaultdict(list)\n",
    "        groupcount=collections.Counter()\n",
    "        for i,x in enumerate(beforeItems):\n",
    "            for j in x:\n",
    "                if group[j]==group[i]:\n",
    "                    continue\n",
    "                grouplist[group[j]].append(group[i])\n",
    "                groupcount[group[i]]+=1\n",
    "        groupsort=[i for i in range(id+1) if groupcount[i]==0]\n",
    "        queue=deque(groupsort)\n",
    "        while queue:\n",
    "            x=queue.popleft()\n",
    "            for i in grouplist[x]:\n",
    "                groupcount[i]-=1\n",
    "                if groupcount[i]==0:\n",
    "                    queue.append(i)\n",
    "                    groupsort.append(i)\n",
    "        if len(groupsort)!=id+1:\n",
    "            return []\n",
    "\n",
    "        #映射\n",
    "        fenqu=collections.defaultdict(list)\n",
    "        ans=[]\n",
    "        for i in itemsort:\n",
    "            fenqu[group[i]].append(i)\n",
    "        for i in groupsort:\n",
    "            ans.extend(fenqu[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        p = list(range(n))\n",
    "        d = dict()\n",
    "        for i,g in enumerate(group):\n",
    "            if g == -1: continue\n",
    "            if g not in d:\n",
    "                d[g] = [i]\n",
    "            else:\n",
    "                d[g].append(i)\n",
    "                p[i] = d[g][0]\n",
    "        \n",
    "        G = [[] for _ in range(n)]\n",
    "        for i,g in enumerate(group):\n",
    "            if g == -1:\n",
    "                G[i] = set(p[j] for j in beforeItems[i])\n",
    "        \n",
    "        def sortGroup(x):\n",
    "            p0 = p[x[0]]\n",
    "            prev = set()\n",
    "            deg = {i:0 for i in x}\n",
    "            for j in x:\n",
    "                for k in beforeItems[j]:\n",
    "                    if k in deg:\n",
    "                        G[j].append(k)\n",
    "                        deg[k] += 1\n",
    "                    else:\n",
    "                        prev.add(p[k])\n",
    "            q = [i for i,v in deg.items() if v == 0]\n",
    "            ix = 0\n",
    "            while ix < len(q):\n",
    "                j = q[ix]\n",
    "                ix += 1\n",
    "                for k in G[j]:\n",
    "                    deg[k] -= 1\n",
    "                    if deg[k] == 0:\n",
    "                        q.append(k)\n",
    "            G[p0] = prev\n",
    "            return q\n",
    "        \n",
    "        gp = dict()\n",
    "        for x in d.values():\n",
    "            i = x[0]\n",
    "            gp[i] = sortGroup(x)\n",
    "            if len(gp[i]) != len(x):\n",
    "                return []\n",
    "        \n",
    "        deg = {i:0 for i in set(p)}\n",
    "        for i in deg:\n",
    "            for j in G[i]:\n",
    "                deg[j] += 1\n",
    "        q = [i for i,v in deg.items() if v == 0]\n",
    "        ix = 0\n",
    "        while ix < len(q):\n",
    "            j = q[ix]\n",
    "            ix += 1\n",
    "            for k in G[j]:\n",
    "                deg[k] -= 1\n",
    "                if deg[k] == 0:\n",
    "                    q.append(k)\n",
    "\n",
    "        if len(q) < len(deg):\n",
    "            return []\n",
    "        res = []\n",
    "        for i in reversed(q):\n",
    "            if i in gp:\n",
    "                res.extend(gp[i][::-1])\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        p = list(range(n))\n",
    "        d = dict()\n",
    "        for i,g in enumerate(group):\n",
    "            if g == -1: continue\n",
    "            if g not in d:\n",
    "                d[g] = [i]\n",
    "            else:\n",
    "                d[g].append(i)\n",
    "                p[i] = d[g][0]\n",
    "        \n",
    "        G = [[] for _ in range(n)]\n",
    "        for i,g in enumerate(group):\n",
    "            if g == -1:\n",
    "                G[i] = set(p[j] for j in beforeItems[i])\n",
    "\n",
    "        def topoSort(deg):\n",
    "            q = [i for i,v in deg.items() if v == 0]\n",
    "            ix = 0\n",
    "            while ix < len(q):\n",
    "                j = q[ix]\n",
    "                ix += 1\n",
    "                for k in G[j]:\n",
    "                    deg[k] -= 1\n",
    "                    if deg[k] == 0:\n",
    "                        q.append(k)\n",
    "            return q\n",
    "        \n",
    "        def sortGroup(x):\n",
    "            p0 = p[x[0]]\n",
    "            prev = set()\n",
    "            deg = {i:0 for i in x}\n",
    "            for j in x:\n",
    "                for k in beforeItems[j]:\n",
    "                    if k in deg:\n",
    "                        G[j].append(k)\n",
    "                        deg[k] += 1\n",
    "                    else:\n",
    "                        prev.add(p[k])\n",
    "            q = topoSort(deg)\n",
    "            G[p0] = prev\n",
    "            return q\n",
    "        \n",
    "        gp = dict()\n",
    "        for x in d.values():\n",
    "            i = x[0]\n",
    "            gp[i] = sortGroup(x)\n",
    "            if len(gp[i]) != len(x):\n",
    "                return []\n",
    "        \n",
    "        deg = {i:0 for i in set(p)}\n",
    "        for i in deg:\n",
    "            for j in G[i]:\n",
    "                deg[j] += 1\n",
    "        q = topoSort(deg)\n",
    "\n",
    "        if len(q) < len(deg):\n",
    "            return []\n",
    "        res = []\n",
    "        for i in reversed(q):\n",
    "            if i in gp:\n",
    "                res.extend(gp[i][::-1])\n",
    "            else:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        degree = {}\n",
    "        items = defaultdict(list)\n",
    "        for i, g in enumerate(group):\n",
    "            items[g].append(i)\n",
    "            key = i if g == -1 else g+n\n",
    "            degree[key] = 0\n",
    "        deg = defaultdict(int)\n",
    "        for i, before in enumerate(beforeItems):\n",
    "            x = i if group[i] == -1 else group[i]+n\n",
    "            for v in before:\n",
    "                y = v if group[v] == -1 else group[v]+n\n",
    "                # 团队内部\n",
    "                if x == y:\n",
    "                    graph[v].append(i)\n",
    "                    deg[i] += 1\n",
    "                    continue\n",
    "                graph[y].append(x)\n",
    "                degree[x] += 1\n",
    "        q = deque(k for k, v in degree.items() if v == 0)\n",
    "        def f(x) -> list:\n",
    "            ans = []\n",
    "            q = deque(v for v in items[x] if deg[v] == 0)\n",
    "            while q:\n",
    "                v = q.popleft()\n",
    "                ans.append(v)\n",
    "                for y in graph[v]:\n",
    "                    deg[y] -= 1\n",
    "                    if not deg[y]:\n",
    "                        q.append(y)\n",
    "            return ans\n",
    "        res = []\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            if x < n:\n",
    "                res.append(x)\n",
    "            else:\n",
    "                path = f(x-n)\n",
    "                if len(path) != len(items[x-n]):\n",
    "                    return []\n",
    "                res += path\n",
    "            for y in graph[x]:\n",
    "                degree[y] -= 1\n",
    "                if not degree[y]:\n",
    "                    q.append(y)\n",
    "        return res if len(res) == n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        groups = defaultdict(set)  #属于同组的构成一个集合，-1属于散人合集，其它集合都是在项目序号基础上+ m + n\n",
    "        d = {}  #通过项目查所在组，散人属于自己\n",
    "        for i, j in enumerate(group):\n",
    "            if j == -1:\n",
    "                groups[-1].add(i)\n",
    "                d[i] = i\n",
    "            else:\n",
    "                groups[j + m + n].add(i)\n",
    "                d[i] = j + m + n\n",
    "        total = set()\n",
    "        for k, v in d.items():\n",
    "            total.add(v)\n",
    "\n",
    "        innerCmp = defaultdict(list)  #内部排序合集  比如： innerCmp[10] = [[3, 6], [4, 6]]\n",
    "        outerCmp = []  #外部排序   比如： [10, 1, 11, 0, 7]\n",
    "        for i, j in enumerate(beforeItems):\n",
    "            if not j:\n",
    "                continue\n",
    "            for k in j:\n",
    "                if d[i] == d[k]:\n",
    "                    innerCmp[d[i]].append([i, k])\n",
    "                else:\n",
    "                    outerCmp.append([d[i], d[k]])\n",
    "        innerSort = defaultdict(list)   #内部排序 比如： innerSort = [6, 3, 4]\n",
    "        for idx, cmp in innerCmp.items():\n",
    "            ln = len(groups[idx])\n",
    "            # vis = set()\n",
    "            res = []\n",
    "            dq = deque()\n",
    "            degin = Counter()\n",
    "            g = defaultdict(list)\n",
    "            for x, y in cmp:\n",
    "                degin[y] += 1\n",
    "                g[x].append(y)\n",
    "            for item in groups[idx]:\n",
    "                if degin[item] == 0:\n",
    "                    dq.append(item)\n",
    "            while dq:\n",
    "                tmp = dq.popleft()\n",
    "                # vis.add(tmp)\n",
    "                res.append(tmp)\n",
    "                for nxt in g[tmp]:\n",
    "                    degin[nxt] -= 1\n",
    "                    if degin[nxt] == 0:\n",
    "                        dq.append(nxt)\n",
    "            if len(res) != ln:\n",
    "                return []\n",
    "            res = res[::-1]\n",
    "            innerSort[idx] = res[::]\n",
    "        ln = len(groups[-1]) + len(groups) - 1\n",
    "        # vis = set()\n",
    "        res = []\n",
    "        dq = deque()\n",
    "        degin = Counter()\n",
    "        g = defaultdict(list)\n",
    "        for x, y in outerCmp:\n",
    "            degin[y] += 1\n",
    "            g[x].append(y)\n",
    "        for item in total:\n",
    "            if degin[item] == 0:\n",
    "                dq.append(item)\n",
    "        while dq:\n",
    "            tmp = dq.popleft()\n",
    "            # vis.add(tmp)\n",
    "            res.append(tmp)\n",
    "            for nxt in g[tmp]:\n",
    "                degin[nxt] -= 1\n",
    "                if degin[nxt] == 0:\n",
    "                    dq.append(nxt)\n",
    "        if len(res) != ln:\n",
    "            return []\n",
    "        res = res[::-1]\n",
    "        ans = []\n",
    "        for i in res:\n",
    "            if i < m + n:\n",
    "                ans.append(i)\n",
    "            else:\n",
    "                if i in innerSort:\n",
    "                    ans.extend(innerSort[i])\n",
    "                else:\n",
    "                    ans.extend(list(groups[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        gnodes = defaultdict(list) \n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m \n",
    "                gnodes[m].append(i)\n",
    "                m+=1 \n",
    "            else:\n",
    "                gnodes[group[i]].append(i) \n",
    "\n",
    "        g1 = defaultdict(list) \n",
    "        g2 = defaultdict(list) \n",
    "        indeg1 = [0] * n \n",
    "        indeg2 = [0] * m \n",
    "        for i, vec in enumerate(beforeItems):\n",
    "            for v in vec:\n",
    "                g1[v].append(i)\n",
    "                indeg1[i] += 1\n",
    "                if group[v] != group[i]:\n",
    "                    g2[group[v]].append(group[i]) \n",
    "                    indeg2[group[i]] += 1\n",
    "        Q = deque() \n",
    "        arr = []\n",
    "        for i in range(m):\n",
    "            if indeg2[i] == 0:\n",
    "                Q.append(i) \n",
    "        while Q:\n",
    "            u = Q.popleft() \n",
    "            arr.append(u)\n",
    "            for v in g2[u]:\n",
    "                indeg2[v]-=1\n",
    "                if indeg2[v] == 0:\n",
    "                    Q.append(v) \n",
    "        \n",
    "        if len(arr) < m:\n",
    "            return [] \n",
    "        def topsort(g, indeg, nodes):\n",
    "            Q = deque()\n",
    "            for i in nodes:\n",
    "                if indeg[i] == 0:\n",
    "                    Q.append(i)\n",
    "            ans = []\n",
    "            while Q:\n",
    "                u = Q.popleft() \n",
    "                ans.append(u) \n",
    "                for v in g[u]:\n",
    "                    indeg[v] -= 1\n",
    "                    if indeg[v] == 0 and group[v] == group[u]:\n",
    "                        Q.append(v) \n",
    "            return ans \n",
    "        \n",
    "        ans = [] \n",
    "        for i in arr:\n",
    "            brr = topsort(g1, indeg1, gnodes[i])\n",
    "            #print(brr) \n",
    "            if len(brr) < len(gnodes[i]):\n",
    "                return [] \n",
    "            ans.extend(brr) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        def topological(edges, indegree):\n",
    "            n = len(indegree)\n",
    "            q = [i for i in range(n) if indegree[i] == 0]\n",
    "            res = list()\n",
    "            while q:\n",
    "                u = q.pop(0)\n",
    "                res.append(u)\n",
    "                for v in edges[u]:\n",
    "                    indegree[v] -= 1\n",
    "                    if indegree[v] == 0:\n",
    "                        q.append(v)\n",
    "            return res if len(res) == n else []\n",
    "    \n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "        item_edges = collections.defaultdict(list)\n",
    "        item_indegree = [0] * n\n",
    "        for u in range(n):\n",
    "            for v in beforeItems[u]:\n",
    "                if u not in item_edges[v]:\n",
    "                    item_edges[v].append(u)\n",
    "                    item_indegree[u] += 1\n",
    "                    \n",
    "        group_edges = collections.defaultdict(list)\n",
    "        group_indegree = [0] * m\n",
    "        for i in range(n):\n",
    "            cur_group = group[i]\n",
    "            for u in beforeItems[i]:\n",
    "                pre_group = group[u]\n",
    "                if cur_group != pre_group and cur_group not in group_edges[pre_group]:\n",
    "                    group_edges[pre_group].append(cur_group)\n",
    "                    group_indegree[cur_group] += 1\n",
    "        \n",
    "        item_topolist = topological(item_edges, item_indegree)\n",
    "        group_topolist = topological(group_edges, group_indegree)\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for item in item_topolist:\n",
    "            hashmap[group[item]].append(item)\n",
    "        res = []\n",
    "        for group in group_topolist:\n",
    "            res += hashmap[group]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        for i,g in enumerate(group):\n",
    "            if g == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "\n",
    "        group_2_proj = [[] for _ in range(m)]\n",
    "        for proj, g in enumerate(group):\n",
    "            group_2_proj[g].append(proj)\n",
    "        group_2_BFGroup = [set() for _ in range(m)]\n",
    "\n",
    "        for g in range(m):\n",
    "            for p in group_2_proj[g]:\n",
    "                for bfp in beforeItems[p]:\n",
    "                    bfg = group[bfp]\n",
    "                    group_2_BFGroup[g].add(bfg)\n",
    "\n",
    "        finish_group_lst = []\n",
    "        finish_group_set = set()\n",
    "        ans = []\n",
    "        while len(group_2_BFGroup) > len(finish_group_lst):\n",
    "            flag = False\n",
    "            for g, BFGset in enumerate(group_2_BFGroup):\n",
    "                if g in finish_group_set:\n",
    "                    continue\n",
    "                for BFG in BFGset:\n",
    "                    if BFG != g and BFG not in finish_group_set:\n",
    "                        break\n",
    "                else:\n",
    "                    finish_proj_lst = []\n",
    "                    finish_proj_set = set()\n",
    "                    while True:\n",
    "                        for p in group_2_proj[g]:\n",
    "                            if p in finish_proj_set:\n",
    "                                continue\n",
    "                            for BFp in beforeItems[p]:\n",
    "                                if BFp not in finish_proj_set and group[BFp] not in finish_group_set:\n",
    "                                    break\n",
    "                            else:\n",
    "                                finish_proj_lst.append(p)\n",
    "                                finish_proj_set.add(p)\n",
    "                                break\n",
    "                        else:\n",
    "                            if len(finish_proj_lst) == len(group_2_proj[g]):\n",
    "                                break\n",
    "                            return []\n",
    "                    finish_group_lst.append(g)\n",
    "                    finish_group_set.add(g)\n",
    "                    ans += finish_proj_lst\n",
    "                    flag = True\n",
    "            if not flag:\n",
    "                return []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        def toposort(edges, indegree):\n",
    "            n = len(indegree)\n",
    "            q = [i for i in range(n) if indegree[i] == 0]\n",
    "            res = list()\n",
    "            while q:\n",
    "                u = q.pop(0)\n",
    "                res.append(u)\n",
    "                for v in edges[u]:\n",
    "                    indegree[v] -= 1\n",
    "                    if indegree[v] == 0:\n",
    "                        q.append(v)\n",
    "            return res if len(res) == n else []\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m += 1\n",
    "        item_edges, group_edges = collections.defaultdict(list), collections.defaultdict(list)\n",
    "        item_indeg, group_indeg = [0] * n, [0] * m\n",
    "        for i in range(n):\n",
    "            for u in beforeItems[i]:\n",
    "                item_edges[u].append(i)\n",
    "                item_indeg[i] += 1\n",
    "        for i in range(n):\n",
    "            cur_group = group[i]\n",
    "            for u in beforeItems[i]:\n",
    "                prev_group = group[u]\n",
    "                if cur_group != prev_group:\n",
    "                    group_edges[prev_group].append(cur_group)\n",
    "                    group_indeg[cur_group] += 1\n",
    "        item_list, group_list = toposort(item_edges, item_indeg), toposort(group_edges, group_indeg)\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for item in item_list:\n",
    "            hashmap[group[item]].append(item)\n",
    "        res = []\n",
    "        for group in group_list:\n",
    "            res += hashmap[group]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self,items,indeg,graph):\n",
    "        q = deque()\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indeg[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            ans.append(t)\n",
    "            for nextnode in graph[t]:\n",
    "                indeg[nextnode] -= 1\n",
    "                if not indeg[nextnode]:\n",
    "                    q.append(nextnode)\n",
    "        return ans\n",
    "             \n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m\n",
    "                m+=1\n",
    "        project_indeg = defaultdict(int)\n",
    "        group_indeg = defaultdict(int)\n",
    "        project_graph = defaultdict(list)\n",
    "        group_graph = defaultdict(list)\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            group_project[group[i]].append(i)\n",
    "            for pre in beforeItems[i]:\n",
    "                if group[pre] != group[i]:\n",
    "                    group_indeg[group[i]]+=1\n",
    "                    group_graph[group[pre]].append(group[i])\n",
    "                else:\n",
    "                    project_indeg[i] +=1\n",
    "                    project_graph[pre].append(i)\n",
    "        ans = []\n",
    "        group_queue = self.tp_sort([i for i in range(m)], group_indeg, group_graph)\n",
    "        if len(group_queue) != m:\n",
    "            return []\n",
    "        for t in group_queue:\n",
    "            project_queue = self.tp_sort(group_project[t],project_indeg,project_graph)\n",
    "            if len(project_queue) != len(group_project[t]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n, m, group, beforeItems) :\n",
    "        # 为不属于任何小组的项目设置一个虚拟组名\n",
    "        j=m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1: \n",
    "                group[i]=j\n",
    "                j+=1\n",
    "        # 小组拓扑：in={小组:需要排在前面的小组} out={小组:需要排在后面的小组}\n",
    "        groups=list(set(group))\n",
    "        # 注意:使用set避免重复\n",
    "        group_in, group_out = defaultdict(set), defaultdict(set) \n",
    "        for i in range(n):\n",
    "            for pre_i in beforeItems[i]:\n",
    "                if group[pre_i]!=group[i]: # 注意: 不等时才加入\n",
    "                    group_in[group[i]].add(group[pre_i])\n",
    "                    group_out[group[pre_i]].add(group[i])\n",
    "        indegree={g:len(group_in[g]) for g in groups}\n",
    "        que=[g for g in groups if indegree[g]==0]\n",
    "        order_group=[]\n",
    "        while que:\n",
    "            g = que.pop()\n",
    "            order_group.append(g)\n",
    "            for g_post in group_out[g]:\n",
    "                indegree[g_post]-=1\n",
    "                if indegree[g_post]==0: que.append(g_post)\n",
    "        if len(order_group)<len(groups): return []\n",
    "        # 建立字典 {小组: 组内项目}\n",
    "        group_item=defaultdict(list)\n",
    "        for i in range(len(group)):\n",
    "            group_item[group[i]].append(i)\n",
    "        # 组内项目拓扑排序 遍历小组按顺序执行\n",
    "        execute=[]\n",
    "        for g in order_group:\n",
    "            item_in, item_out = defaultdict(list), defaultdict(list)\n",
    "            for i in group_item[g]:\n",
    "                for pre_i in beforeItems[i]:\n",
    "                    if pre_i in group_item[g]: # 注意: 同一个组才加入\n",
    "                        item_in[i].append(pre_i)\n",
    "                        item_out[pre_i].append(i)\n",
    "            indegree={i:len(item_in[i]) for i in group_item[g]}\n",
    "            que=[i for i in group_item[g] if indegree[i]==0]\n",
    "            temp=[]\n",
    "            while que:\n",
    "                i = que.pop()\n",
    "                temp.append(i)\n",
    "                for i_post in item_out[i]:\n",
    "                    indegree[i_post]-=1\n",
    "                    if indegree[i_post]==0: que.append(i_post)\n",
    "            if len(temp)<len(group_item[g]): return []\n",
    "            execute+=temp\n",
    "        return execute\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:\n",
    "                group_project[num_group].append(i)\n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            else:\n",
    "                group_project[group[i]].append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                else:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = []\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort if len(top_sort)==len(nodes) else None\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if sorted_group==None:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if cur==None:\n",
    "                return []\n",
    "            res += cur\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 拓扑排序\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def tp_sort(self,items,indegree,neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "            \n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # 将无人负责的组分给一个不重复的id组别\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "        \n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "        \n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in beforeItems[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    #项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)],group_indegree,group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "        \n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree,project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        def tp_sort(items, indegree, neighbors):\n",
    "            q = collections.deque([])\n",
    "            ans = []\n",
    "            for item in items:\n",
    "                if not indegree[item]:\n",
    "                    q.append(item)\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                ans.append(cur)\n",
    "\n",
    "                for neighbor in neighbors[cur]:\n",
    "                    indegree[neighbor] -= 1\n",
    "                    if not indegree[neighbor]:\n",
    "                        q.append(neighbor)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in beforeItems[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tpsort(self, items, indgree, nbs):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "\n",
    "        for item in items:\n",
    "            if indgree[item] == 0:\n",
    "                q.append(item)\n",
    "\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neib in nbs[cur]:\n",
    "                indgree[neib] -= 1\n",
    "                if indgree[neib] == 0:\n",
    "                    q.append(neib)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        mg = m\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = mg\n",
    "                mg += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            # 每个组都有谁\n",
    "            group_projects[group[i]].append(i)\n",
    "\n",
    "            for pre in beforeItems[i]:\n",
    "                if group[pre] != group[i]:\n",
    "                    group_indegree[group[i]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[i])\n",
    "                else:\n",
    "                    ## 同一个组\n",
    "                    project_indegree[i] += 1\n",
    "                    project_neighbors[pre].append(i)\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tpsort([i for i in range(mg)], group_indegree, group_neighbors)\n",
    "\n",
    "        # 存在环，可以通过拓补排序输出不全判断\n",
    "        if len(group_queue) != mg:\n",
    "            return []\n",
    "\n",
    "        for gourp_id in group_queue:\n",
    "            project_queue = self.tpsort(group_projects[gourp_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[gourp_id]):\n",
    "                return []\n",
    "\n",
    "            ans += project_queue\n",
    "        return ans\n",
    "\n",
    "\n",
    "        items = [i for i in range(n)]\n",
    "\n",
    "        return self.tpsort(items, indgree, nbs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "        \n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "\n",
    "        # This is for categorized\n",
    "        group_project = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_project[group[project]].append(project)\n",
    "\n",
    "            for pre in beforeItems[project]:\n",
    "                # project has another group's project dependenies\n",
    "                if group[pre] != group[project]:\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                # in group dependencies\n",
    "                else:\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "        \n",
    "        for group_id in group_queue:\n",
    "            project_queue = self.tp_sort(group_project[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_project[group_id]):\n",
    "                return []\n",
    "\n",
    "            ans += project_queue\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 作者：lucifer\n",
    "# 链接：https://leetcode.cn/problems/sort-items-by-groups-respecting-dependencies/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tpsort(self,items,indgree,nei):\n",
    "        q = deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indgree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for ne in nei[cur]:\n",
    "                indgree[ne] -= 1\n",
    "                if not indgree[ne]:\n",
    "                    q.append(ne)\n",
    "        return ans \n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        #copy\n",
    "        mxgroupid = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = mxgroupid\n",
    "                mxgroupid += 1\n",
    "        project_indegree = defaultdict(int)\n",
    "        group_indgree = defaultdict(int)\n",
    "        project_nei = defaultdict(list)\n",
    "        group_nei = defaultdict(list)\n",
    "        group_projects = defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    group_indgree[group[project]] += 1\n",
    "                    group_nei[group[pre]].append(group[project])      \n",
    "                else:\n",
    "                    project_indegree[project] += 1\n",
    "                    project_nei[pre].append(project)\n",
    "        ans  = []\n",
    "        group_queue = self.tpsort([i for i in range(mxgroupid)],group_indgree,group_nei)\n",
    "        if len(group_queue) != mxgroupid:\n",
    "            return []\n",
    "        for group_id in group_queue:\n",
    "            project_queue = self.tpsort(group_projects[group_id],project_indegree,project_nei)\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tp_sort(self, items, indegree, neighbors):\n",
    "        q = collections.deque([])\n",
    "        ans = []\n",
    "        for item in items:\n",
    "            if not indegree[item]:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if not indegree[neighbor]:\n",
    "                    q.append(neighbor)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:\n",
    "        max_group_id = m\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "\n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in pres[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    # 小组关系图\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    # 项目关系图\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        if len(group_queue) != max_group_id:\n",
    "            return []\n",
    "\n",
    "        for group_id in group_queue:\n",
    "\n",
    "            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            ans += project_queue\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # def tp_sort(items, indegree, neighbors):\n",
    "        #     q = collections.deque([])\n",
    "        #     ans = []\n",
    "        #     for item in items:\n",
    "        #         if not indegree[item]:\n",
    "        #             q.append(item)\n",
    "        #     while q:\n",
    "        #         cur = q.popleft()\n",
    "        #         ans.append(cur)\n",
    "\n",
    "        #         for neighbor in neighbors[cur]:\n",
    "        #             indegree[neighbor] -= 1\n",
    "        #             if not indegree[neighbor]:\n",
    "        #                 q.append(neighbor)\n",
    "\n",
    "        #     return ans\n",
    "\n",
    "        # max_group_id = m\n",
    "        # for project in range(n):\n",
    "        #     if group[project] == -1:\n",
    "        #         group[project] = max_group_id\n",
    "        #         max_group_id += 1\n",
    "\n",
    "        # project_indegree = collections.defaultdict(int)\n",
    "        # group_indegree = collections.defaultdict(int)\n",
    "        # project_neighbors = collections.defaultdict(list)\n",
    "        # group_neighbors = collections.defaultdict(list)\n",
    "        # group_projects = collections.defaultdict(list)\n",
    "\n",
    "        # for project in range(n):\n",
    "        #     group_projects[group[project]].append(project)\n",
    "\n",
    "        #     for pre in beforeItems[project]:\n",
    "        #         if group[pre] != group[project]:\n",
    "        #             # 小组关系图\n",
    "        #             group_indegree[group[project]] += 1\n",
    "        #             group_neighbors[group[pre]].append(group[project])\n",
    "        #         else:\n",
    "        #             # 项目关系图\n",
    "        #             project_indegree[project] += 1\n",
    "        #             project_neighbors[pre].append(project)\n",
    "\n",
    "        # ans = []\n",
    "\n",
    "        # group_queue = tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        # if len(group_queue) != max_group_id:\n",
    "        #     return []\n",
    "\n",
    "        # for group_id in group_queue:\n",
    "\n",
    "        #     project_queue = tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "        #     if len(project_queue) != len(group_projects[group_id]):\n",
    "        #         return []\n",
    "        #     ans += project_queue\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        from collections import defaultdict, deque\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:          \n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            \n",
    "\n",
    "        for i in range(n):\n",
    "            group_project[group[i]].append(i)\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                else:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = deque()\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.popleft()\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if len(sorted_group) != num_group:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if len(cur)!=len(group_project[group]):\n",
    "                return []\n",
    "            res += cur\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:\n",
    "                group_project[num_group].append(i)\n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            else:\n",
    "                group_project[group[i]].append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i] not in graph_group[group[node]] and group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                if group[i]==group[node]:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = []\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort if len(top_sort)==len(nodes) else None\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if sorted_group==None:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if cur==None:\n",
    "                return []\n",
    "            res += cur\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:\n",
    "                group_project[num_group].append(i)\n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            else:\n",
    "                group_project[group[i]].append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i] not in graph_group[group[node]] and group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                if group[i]==group[node]:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = []\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort if len(top_sort)==len(nodes) else None\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if sorted_group==None:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if cur==None:\n",
    "                return []\n",
    "            res += cur[:]\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # def tp_sort(items, indegree, neighbors):\n",
    "        #     q = collections.deque([])\n",
    "        #     ans = []\n",
    "        #     for item in items:\n",
    "        #         if not indegree[item]:\n",
    "        #             q.append(item)\n",
    "        #     while q:\n",
    "        #         cur = q.popleft()\n",
    "        #         ans.append(cur)\n",
    "\n",
    "        #         for neighbor in neighbors[cur]:\n",
    "        #             indegree[neighbor] -= 1\n",
    "        #             if not indegree[neighbor]:\n",
    "        #                 q.append(neighbor)\n",
    "\n",
    "        #     return ans\n",
    "\n",
    "        # max_group_id = m\n",
    "        # for project in range(n):\n",
    "        #     if group[project] == -1:\n",
    "        #         group[project] = max_group_id\n",
    "        #         max_group_id += 1\n",
    "\n",
    "        # project_indegree = collections.defaultdict(int)\n",
    "        # group_indegree = collections.defaultdict(int)\n",
    "        # project_neighbors = collections.defaultdict(list)\n",
    "        # group_neighbors = collections.defaultdict(list)\n",
    "        # group_projects = collections.defaultdict(list)\n",
    "\n",
    "        # for project in range(n):\n",
    "        #     group_projects[group[project]].append(project)\n",
    "\n",
    "        #     for pre in beforeItems[project]:\n",
    "        #         if group[pre] != group[project]:\n",
    "        #             # 小组关系图\n",
    "        #             group_indegree[group[project]] += 1\n",
    "        #             group_neighbors[group[pre]].append(group[project])\n",
    "        #         else:\n",
    "        #             # 项目关系图\n",
    "        #             project_indegree[project] += 1\n",
    "        #             project_neighbors[pre].append(project)\n",
    "\n",
    "        # ans = []\n",
    "\n",
    "        # group_queue = tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        # if len(group_queue) != max_group_id:\n",
    "        #     return []\n",
    "\n",
    "        # for group_id in group_queue:\n",
    "\n",
    "        #     project_queue = tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "        #     if len(project_queue) != len(group_projects[group_id]):\n",
    "        #         return []\n",
    "        #     ans += project_queue\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        from collections import defaultdict\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:          \n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            \n",
    "\n",
    "        for i in range(n):\n",
    "            group_project[group[i]].append(i)\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                else:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = []\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort if len(top_sort)==len(nodes) else None\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if sorted_group==None:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if cur==None:\n",
    "                return []\n",
    "            res += cur\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        #解题思路：\n",
    "        #先计算出每个小组的成员\n",
    "        #由于同一个小组的成员在列表中相邻，因此，某成员的先修项目也是该组的先修项目\n",
    "        #0\n",
    "        #1->6\n",
    "        #7\n",
    "        #2,5 ->5\n",
    "        #3,4,6 ->3,6\n",
    "        #解析：\n",
    "        #两个拓扑排序，组内，组间\n",
    "        \n",
    "        max_group_id = m #给没有组的成员分配组号\n",
    "        for project in range(n):\n",
    "            if group[project] == -1:\n",
    "                group[project] = max_group_id\n",
    "                max_group_id += 1\n",
    "        \n",
    "        project_indegree = collections.defaultdict(int)\n",
    "        group_indegree = collections.defaultdict(int)\n",
    "        project_neighbors = collections.defaultdict(list)\n",
    "        group_neighbors = collections.defaultdict(list)\n",
    "        group_projects = collections.defaultdict(list)\n",
    "\n",
    "        for project in range(n):\n",
    "            group_projects[group[project]].append(project)\n",
    "\n",
    "            for pre in beforeItems[project]:\n",
    "                if group[pre] != group[project]:\n",
    "                    #组间关系\n",
    "                    group_indegree[group[project]] += 1\n",
    "                    group_neighbors[group[pre]].append(group[project])\n",
    "                else:\n",
    "                    #组内关系\n",
    "                    project_indegree[project] += 1\n",
    "                    project_neighbors[pre].append(project)\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        #组间排序\n",
    "        group_queue = self.tp_sort([i for i in range(max_group_id)],group_indegree,group_neighbors)\n",
    "        if len(group_queue) != max_group_id: #存在环\n",
    "            return []\n",
    "        \n",
    "        #组内排序\n",
    "        for group_id in group_queue:\n",
    "            project_queue = self.tp_sort(group_projects[group_id],project_indegree,project_neighbors)\n",
    "            if len(project_queue) != len(group_projects[group_id]):\n",
    "                return []\n",
    "            res += project_queue\n",
    "\n",
    "        return res\n",
    "\n",
    "    def tp_sort(self,items,indegree,neighbors):\n",
    "        q = []\n",
    "        ans = []\n",
    "        #注意，只对items中的元素进行拓扑排序\n",
    "        for item in items:\n",
    "            if indegree[item] == 0:\n",
    "                q.append(item)\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            ans.append(cur)\n",
    "            for neighbor in neighbors[cur]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    q.append(neighbor)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        # def tp_sort(items, indegree, neighbors):\n",
    "        #     q = collections.deque([])\n",
    "        #     ans = []\n",
    "        #     for item in items:\n",
    "        #         if not indegree[item]:\n",
    "        #             q.append(item)\n",
    "        #     while q:\n",
    "        #         cur = q.popleft()\n",
    "        #         ans.append(cur)\n",
    "\n",
    "        #         for neighbor in neighbors[cur]:\n",
    "        #             indegree[neighbor] -= 1\n",
    "        #             if not indegree[neighbor]:\n",
    "        #                 q.append(neighbor)\n",
    "\n",
    "        #     return ans\n",
    "\n",
    "        # max_group_id = m\n",
    "        # for project in range(n):\n",
    "        #     if group[project] == -1:\n",
    "        #         group[project] = max_group_id\n",
    "        #         max_group_id += 1\n",
    "\n",
    "        # project_indegree = collections.defaultdict(int)\n",
    "        # group_indegree = collections.defaultdict(int)\n",
    "        # project_neighbors = collections.defaultdict(list)\n",
    "        # group_neighbors = collections.defaultdict(list)\n",
    "        # group_projects = collections.defaultdict(list)\n",
    "\n",
    "        # for project in range(n):\n",
    "        #     group_projects[group[project]].append(project)\n",
    "\n",
    "        #     for pre in beforeItems[project]:\n",
    "        #         if group[pre] != group[project]:\n",
    "        #             # 小组关系图\n",
    "        #             group_indegree[group[project]] += 1\n",
    "        #             group_neighbors[group[pre]].append(group[project])\n",
    "        #         else:\n",
    "        #             # 项目关系图\n",
    "        #             project_indegree[project] += 1\n",
    "        #             project_neighbors[pre].append(project)\n",
    "\n",
    "        # ans = []\n",
    "\n",
    "        # group_queue = tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)\n",
    "\n",
    "        # if len(group_queue) != max_group_id:\n",
    "        #     return []\n",
    "\n",
    "        # for group_id in group_queue:\n",
    "\n",
    "        #     project_queue = tp_sort(group_projects[group_id], project_indegree, project_neighbors)\n",
    "\n",
    "        #     if len(project_queue) != len(group_projects[group_id]):\n",
    "        #         return []\n",
    "        #     ans += project_queue\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        from collections import defaultdict\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:          \n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            \n",
    "\n",
    "        for i in range(n):\n",
    "            group_project[group[i]].append(i)\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                else:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = []\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if len(sorted_group) != num_group:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if len(cur)!=len(group_project[group]):\n",
    "                return []\n",
    "            res += cur\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph_group = defaultdict(list)\n",
    "        indegre_group = defaultdict(int)\n",
    "\n",
    "        graph_project = defaultdict(list)\n",
    "        indegre_project = defaultdict(int)\n",
    "\n",
    "        group_project = defaultdict(list)\n",
    "\n",
    "        num_group = m\n",
    "        for i in range(n):\n",
    "            if group[i]==-1:          \n",
    "                group[i]=num_group\n",
    "                num_group += 1\n",
    "            \n",
    "\n",
    "        for i in range(n):\n",
    "            group_project[group[i]].append(i)\n",
    "            for node in beforeItems[i]:\n",
    "                if group[i]!=group[node]:\n",
    "                    graph_group[group[node]].append(group[i])\n",
    "                    indegre_group[group[i]] += 1\n",
    "                else:\n",
    "                    graph_project[node].append(i)\n",
    "                    indegre_project[i] += 1\n",
    "\n",
    "        # print(graph_group, indegre_group)\n",
    "        # print(graph_project, indegre_project)\n",
    "        # print(group_project)\n",
    "        # print(group)\n",
    "\n",
    "        def bfs(nodes, graph, indegre):\n",
    "            queue = []\n",
    "            for node in nodes:\n",
    "                if indegre[node]==0:\n",
    "                    queue.append(node)\n",
    "\n",
    "            top_sort = []\n",
    "            while queue:\n",
    "                x = queue.pop(0)\n",
    "                top_sort.append(x)\n",
    "                for nei in graph[x]:\n",
    "                    indegre[nei]-=1\n",
    "                    if indegre[nei]==0:\n",
    "                        queue.append(nei)\n",
    "            return top_sort if len(top_sort)==len(nodes) else None\n",
    "\n",
    "        sorted_group = bfs(list(range(num_group)), graph_group, indegre_group)\n",
    "        if sorted_group==None:\n",
    "            return []\n",
    "        res = []\n",
    "        for group in sorted_group:\n",
    "            cur = bfs(group_project[group], graph_project, indegre_project)\n",
    "            if cur==None:\n",
    "                return []\n",
    "            res += cur\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group, beforeItems):\n",
    "        node_edge = collections.defaultdict(set)\n",
    "        group_edge = collections.defaultdict(set)\n",
    "        group_du = collections.defaultdict(int)\n",
    "        node_du = collections.defaultdict(int)\n",
    "        group_dict = collections.defaultdict(set)\n",
    "        for u, items in enumerate(beforeItems):\n",
    "            group_1 = group[u]\n",
    "            if group_1 != -1:\n",
    "                group_dict[group_1].add(u)\n",
    "            for v in items:\n",
    "                group_2 = group[v]\n",
    "                if group_2 != -1:\n",
    "                    group_dict[group_2].add(v)\n",
    "                if group_1 == -1:\n",
    "                    if group_2 == -1:\n",
    "                        group_edge[- v - 1].add(- u - 1)\n",
    "                        group_du[- u - 1] += 1\n",
    "                    else:\n",
    "                        group_edge[group_2].add( - u - 1)\n",
    "                        group_du[ - u - 1] += 1\n",
    "                else:\n",
    "                    if group_2 == -1:\n",
    "                        group_edge[- v - 1].add(group_1)\n",
    "                        group_du[group_1] += 1\n",
    "                    else:\n",
    "                        if group_1 != group_2:\n",
    "                            if group_1 not in group_edge[group_2]:\n",
    "                                group_edge[group_2].add(group_1)\n",
    "                                group_du[group_1] += 1\n",
    "                        else:\n",
    "                            node_edge[v].add(u)\n",
    "                            node_du[u] += 1\n",
    "        group_st = set()\n",
    "        ans = []\n",
    "        for u, group_id in enumerate(group):\n",
    "            if group_id == -1:\n",
    "                group_id = - u - 1\n",
    "            if group_du[group_id] == 0:\n",
    "                group_st.add(group_id)\n",
    "        while group_st:\n",
    "            group_id = group_st.pop()\n",
    "            if group_id < 0:\n",
    "                ans.append(- group_id - 1)\n",
    "            else:\n",
    "                node_st = []\n",
    "                for node in group_dict[group_id]:\n",
    "                    if node_du[node] == 0:\n",
    "                        node_st.append(node)\n",
    "                while node_st:\n",
    "                    node = node_st.pop()\n",
    "                    ans.append(node)\n",
    "                    for v in node_edge[node]:\n",
    "                        node_du[v] -= 1\n",
    "                        if node_du[v] == 0:\n",
    "                            node_st.append(v)\n",
    "            for v in group_edge[group_id]:\n",
    "                group_du[v] -= 1\n",
    "                if group_du[v] == 0:\n",
    "                    group_st.add(v)\n",
    "        if len(ans) == n:\n",
    "            return ans\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:\n",
    "        def topological_sort(graph, indegree):\n",
    "            queue = [node for node in range(len(indegree)) if indegree[node] == 0]\n",
    "            res = []\n",
    "            while queue:\n",
    "                node = queue.pop(0)\n",
    "                res.append(node)\n",
    "                for neighbor in graph[node]:\n",
    "                    indegree[neighbor] -= 1\n",
    "                    if indegree[neighbor] == 0:\n",
    "                        queue.append(neighbor)\n",
    "            return res if len(res) == len(indegree) else []\n",
    "\n",
    "        group_graph = defaultdict(list)\n",
    "        item_graph = defaultdict(list)\n",
    "        group_indegree = [0] * (m + n)\n",
    "        item_indegree = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if group[i] == -1:\n",
    "                group[i] = m + i\n",
    "\n",
    "        for i in range(n):\n",
    "            for before in beforeItems[i]:\n",
    "                if group[i] == group[before]:\n",
    "                    item_graph[before].append(i)\n",
    "                    item_indegree[i] += 1\n",
    "                else:\n",
    "                    group_graph[group[before]].append(group[i])\n",
    "                    group_indegree[group[i]] += 1\n",
    "\n",
    "        group_order = topological_sort(group_graph, group_indegree)\n",
    "        if not group_order: return []\n",
    "\n",
    "        item_order = topological_sort(item_graph, item_indegree)\n",
    "        if not item_order: return []\n",
    "\n",
    "        group_item = defaultdict(list)\n",
    "        for item in item_order:\n",
    "            group_item[group[item]].append(item)\n",
    "\n",
    "        res = []\n",
    "        for group in group_order:\n",
    "            res += group_item[group]\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
